package main.java.data_structure;

import main.java.utils.SortTestHelper;

import java.util.Random;

/**
 * @author Wrb
 * @date 2019/5/28 15:08
 * 从1开始索引一个堆
 */
public class MaxHeap{
	private int[] data;
	private int count;
	private int capacity;

	public MaxHeap(int capacity) {
		this.data = new int[capacity + 1];
		count = 0;
		this.capacity = capacity;
	}

	public MaxHeap(int[] arr, int n) {
		data = new int[n + 1];
		capacity = n;
		for (int i = 0; i < n; i++) {
			data[i] = arr[i];
		}
		count = n;
		for (int i = count / 2; i >= 1; i--) {
			shiftDown(i);
		}
	}

	public int size() {
		return count;
	}

	public boolean isEmpty() {
		return count == 0;
	}

	/**
	 * 入队 放在最后一个位置，并跟父结点 比较直到有序
	 * @param t
	 */
	public void insert(int t) {
		if (count == capacity) {
			int[] data = new int[2 * capacity + 1];
			System.arraycopy(this.data, 0, data, 0, capacity + 1);
			this.data = data;
			this.capacity = 2 * capacity;
		}
		data[count + 1] = t;
		count++;
		shiftUp(count);
	}

	private void shiftUp(int k) {
		while (k > 1 && data[k / 2] < data[k]) {
			SortTestHelper.swap(data, k, k / 2);
			k /= 2;
		}
	}

	/**
	 * 出队 把第一个元素出队，并且将最后一个元素放在第一个元素重新排序
	 * @return
	 */
	public int extractMax() {
		assert (count > 0);

		int ret = data[1];
		SortTestHelper.swap(data, 1, count);
		count--;
		shiftDown(1);
		return ret;
	}

	private void shiftDown(int k) {
		while (2 * k <= count) {
			int j = 2 * k; //在此循环中，data[k]和data[j]交换位置
			if (j + 1 <= count && data[j + 1] > data[j]) {
				j += 1;
			}
			if (data[k] >= data[j]) {
				break;
			}
			SortTestHelper.swap(data, k, j);
			k = j;
		}
	}

	public void testPrint(){

		if( size() >= 100 ){
			System.out.println("Fancy print can only work for less than 100 int");
			return;
		}

		System.out.println("The Heap size is: " + size());
		System.out.println("data in heap: ");
		for( int i = 1 ; i <= size() ; i ++ ) {
			System.out.print(data[i] + " ");
		}
		System.out.println();
		System.out.println();

		int n = size();
		int max_level = 0;
		int number_per_level = 1;
		while( n > 0 ) {
			max_level += 1;
			n -= number_per_level;
			number_per_level *= 2;
		}

		int max_level_number = (int)Math.pow(2, max_level-1);
		int cur_tree_max_level_number = max_level_number;
		int index = 1;
		for( int level = 0 ; level < max_level ; level ++ ){
			StringBuilder line1 = new StringBuilder();
			for (int k = max_level_number * 3 - 1; k > 0; k--) {
				line1.append(" ");
			}

			int cur_level_number = Math.min(count-(int)Math.pow(2,level)+1,(int)Math.pow(2,level));
			boolean isLeft = true;
			for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index ++ , index_cur_level ++ ){
				putNumberInLine( data[index] , line1 , index_cur_level , cur_tree_max_level_number*3-1 , isLeft );
				isLeft = !isLeft;
			}
			System.out.println(line1);

			if( level == max_level - 1 )
				break;

			StringBuilder line2 = new StringBuilder();
			for (int k = max_level_number * 3 - 1; k > 0; k--) {
				line2.append(" ");
			}
			for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index_cur_level ++ )
				putBranchInLine( line2 , index_cur_level , cur_tree_max_level_number*3-1 );
			System.out.println(line2);

			cur_tree_max_level_number /= 2;
		}
	}

	private void putNumberInLine( int num, StringBuilder line, int index_cur_level, int cur_tree_width, boolean isLeft){

		int sub_tree_width = (cur_tree_width - 1) / 2;
		int offset = index_cur_level * (cur_tree_width+1) + sub_tree_width;
		assert(offset + 1 < line.length());
		if( num >= 10 ) {
			line.replace(offset, offset,"" + num / 10);
			line.replace(offset + 1, offset + 1, "" + num % 10);
		}
		else{
			if( isLeft)
				line.replace(offset, offset, "" + num);
			else
				line.replace(offset + 1, offset + 1, "" + num);
		}
	}

	private void putBranchInLine( StringBuilder line, int index_cur_level, int cur_tree_width){

		int sub_tree_width = (cur_tree_width - 1) / 2;
		int sub_sub_tree_width = (sub_tree_width - 1) / 2;
		int offset_left = index_cur_level * (cur_tree_width+1) + sub_sub_tree_width;
		assert( offset_left + 1 < line.length() );
		int offset_right = index_cur_level * (cur_tree_width+1) + sub_tree_width + 1 + sub_sub_tree_width;
		assert( offset_right < line.length() );

		line.replace(offset_left + 1, offset_left + 1, "/");
		line.replace(offset_right , offset_right , "\\");
	}


	public static void main(String[] args) {
		MaxHeap maxHeap = new MaxHeap(100);
		Random random = new Random();
		for (int i = 0; i < 50; i++) {
			maxHeap.insert(random.nextInt(100));
		}
		while (!maxHeap.isEmpty()) {
			System.out.print(maxHeap.extractMax() + " ");
		}
		maxHeap.testPrint();
	}

}
